package pers.qianyu.month_202101.date_20210114;

import java.util.*;

/**
 * 347. 前 K 个高频元素
 * https://leetcode-cn.com/problems/top-k-frequent-elements/
 *
 * @author mizzle rain
 * @date 2021-01-14 16:43
 */
public class TopKFrequent {
    static class Pair {
        int key, value;

        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<Pair> q = new PriorityQueue<>((p1, p2) -> p2.value - p1.value);
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Integer key : map.keySet()) {
            Integer v = map.get(key);
            q.add(new Pair(key, v));
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = q.poll().key;
        }
        return res;
    }
}
